package main

import (
	"math"
	"strings"
)

// 76. 最小覆盖子串
func main() {
	s := "ADOBECODEBANC"
	t := "ABC"
	window := minWindow(s, t)
	println(window)
}

func minWindow(s string, t string) string {
	ori, cnt := map[byte]int{}, map[byte]int{}
	for i := 0; i < len(t); i++ {
		ori[t[i]]++
	}

	sLen := len(s)
	len := math.MaxInt32
	ansL, ansR := -1, -1

	check := func() bool {
		for k, v := range ori {
			if cnt[k] < v {
				return false
			}
		}
		return true
	}
	for l, r := 0, 0; r < sLen; r++ {
		if r < sLen && ori[s[r]] > 0 {
			cnt[s[r]]++
		}
		for check() && l <= r {
			if r-l+1 < len {
				len = r - l + 1
				ansL, ansR = l, l+len
			}
			if _, ok := ori[s[l]]; ok {
				cnt[s[l]] -= 1
			}
			l++
		}
	}
	if ansL == -1 {
		return ""
	}
	return s[ansL:ansR]
}

// minWindow 小写字母版本
func minWindowMin(s string, t string) string {
	s = strings.ToLower(s)
	t = strings.ToLower(t)
	if len(s) < len(t) || len(t) == 0 {
		return ""
	}

	var check = func(arr1, arr2 [26]int) bool {
		// 判定 arr1 包含 arr2
		for idx, i := range arr1 {
			if i < arr2[idx] {
				return false
			}
		}
		return true
	}

	sArray, tArray := [26]int{}, [26]int{}

	for idx, char := range t {
		tArray[char-'a']++
		sArray[s[idx]-'a']++
	}

	minStr := ""

	if sArray == tArray { // 判断第一个
		return s[0:len(t)]
	}

	prePoint := 0

	for i := 0; i < len(s)-len(t); i++ {
		sArray[s[i+len(t)]-'a']++
		for check(sArray, tArray) {
			subStr := s[prePoint : i+len(t)+1]
			if len(subStr) < len(minStr) || minStr == "" {
				minStr = subStr
			}
			sArray[s[prePoint]-'a']--
			prePoint++
		}
	}

	return minStr
}

// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//
//注意：
//
//对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
//如果 s 中存在这样的子串，我们保证它是唯一的答案。
//
//示例 1：
//
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
//示例 2：
//
//输入：s = "a", t = "a"
//输出："a"
//解释：整个字符串 s 是最小覆盖子串。
//示例 3:
//
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。
